Increasing order search tree [DFS]

Time: O(N); Space: O(H); easy

Given a binary search tree, rearrange the tree in in-order so that the leftmost node in the tree is now the root of the tree, and every node has no left child and only 1 right child.

Example 1:

       5
      / \
    3    6
   / \    \
  2   4    8
 /        / \
1        7   9

Input: root = {TreeNode} [5,3,6,2,4,null,8,1,null,null,null,7,9]

Output: {TreeNode} [1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9]

1
 \
  2
   \
    3
     \
      4
       \
        5
         \
          6
           \
            7
             \
              8
               \
                9

Constraints:

• The number of nodes in the given tree will be between 1 and 100.

• Each node will have a unique integer value from 0 to 1000.

class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

Auxiliary Tools

from graphviz import Graph

class TreeTasks(object):
    def visualize_tree(self, tree):
        def add_nodes_edges(tree, dot=None):
            # Create Graph (not Digraph) object
            if dot is None:
                dot = Graph()
                dot.node(name=str(tree), label=str(tree.val))
            # Add nodes
            if tree.left:
                dot.node(name=str(tree.left), label="."+str(tree.left.val))
                dot.edge(str(tree), str(tree.left))
                dot = add_nodes_edges(tree.left, dot=dot)
            if tree.right:
                dot.node(name=str(tree.right), label=str(tree.right.val)+".")
                dot.edge(str(tree), str(tree.right))
                dot = add_nodes_edges(tree.right, dot=dot)
            return dot
        # Add nodes recursively and create a list of edges
        dot = add_nodes_edges(tree)
        # Visualize the graph
        display(dot)
        return dot

1. Depth First Search

class Solution1(object):
    """
    Time: O(N)
    Space: O(H)
    """
    def increasingBST(self, root):
        """
        :type root: TreeNode
        :rtype: TreeNode
        """
        def increasingBSTHelper(root, tail):
            if not root:
                return tail

            result = increasingBSTHelper(root.left, root)

            root.left = None
            root.right = increasingBSTHelper(root.right, tail)

            return result

        return increasingBSTHelper(root, None)

s = Solution1()

# [5,3,6,2,4,null,8,1,null,null,null,7,9]
root = TreeNode(5)
root.left, root.right = TreeNode(3), TreeNode(6)
root.left.left, root.left.right = TreeNode(2), TreeNode(4)
root.right.right = TreeNode(8)
root.left.left.left = TreeNode(1)
root.right.right.left = TreeNode(7)
root.right.right.right = TreeNode(9)
tree = s.increasingBST(root)
t = TreeTasks()
dot = t.visualize_tree(tree)

See also:

https://leetcode.com/problems/increasing-order-search-tree

https://www.lintcode.com/problem/increasing-order-search-tree/description